/*
提交链接：https://leetcode.cn/problems/minimum-window-substring/submissions/560389670
76. 最小覆盖子串-困难
完成日期：2024/9/1
滑动窗口
*/

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> t_count;  // 存储 t 中每个字符的出现次数
        unordered_map<char, int> window_count;  // 存储当前窗口中每个字符的出现次数
        // 填充 t_count
        for (char c : t) {
            t_count[c]++;
        }
        int required = t_count.size();  // t 中唯一字符的数量
        int formed = 0;  // 当前窗口中符合条件的字符数量
        int l = 0, r = 0;  // 滑动窗口的左右指针
        int min_len = INT_MAX;  // 记录最小长度
        int min_len_start = 0;  // 最小长度子串的起始位置
        while (r < s.size()) {
            char c = s[r];
            window_count[c]++;
            // 如果当前窗口中字符的数量达到了 t 中字符的数量
            if (t_count.find(c) != t_count.end() && window_count[c] == t_count[c]) {
                formed++;
            }
            // 收缩窗口
            while (l <= r && formed == required) {
                char c = s[l];
                // 更新最小长度和最小长度子串的起始位置
                if (r - l + 1 < min_len) {
                    min_len = r - l + 1;
                    min_len_start = l;
                }
                window_count[c]--;
                if (t_count.find(c) != t_count.end() && window_count[c] < t_count[c]) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return min_len == INT_MAX ? "" : s.substr(min_len_start, min_len);
    }
};
